<!DOCTYPE html>
<html lang="zh-CN">

<head>
	<meta charset="UTF-8" />
	<title>算法图解</title>
	<link rel="stylesheet" href="../style/css/article.css">
	<!-- <script src="js/a.js"></script> -->
</head>

<body>
<a id="top" href="#"></a>
<div id="particles-js"></div>
<div class="meta">
<h1>Meta</h1>
<div class="h3i1">
<h3>before reading</h3>
<ul>
<li>Thu Jul 22 14:20:10 CST 2021</li>
<li>在此书之前的上一本书是什么呢, 没错, 是<<大奉打更人>>, 哈, 堕落呀堕落, 看的我头昏脑胀, 需要点新东西给我洗洗脑, 好好读读这本书, 一鼓作气, 不衰不竭.</li>
<li>倒也不必强求用vim做笔记, vim是一个优秀的文本编辑器, 但是针对图片的处理终究有些不便, so, 不强求, 用为知自带的编辑器就好, 对图片处理也比较方便, 读这本图解书应该笔记中会有不少的精彩图解吧, 希望不会让我失望.</li>
</ul>
</div><div class="h3i2">
<h3>after reading</h3>
<ul>
<li>Fri Jul 23 09:41:14 CST 2021</li>
<li><<算法图解:像小说一样有趣的算法入门书>>, 读过全篇, 感觉一般, 作者与出版方对于本书的定位是以图形为讲解媒介的算法入门型书籍, 那我就不提它毫无算法体系的问题了, 单论其入门角度来说, 从二分查找开始到K-nearest neighbours结束, 几乎每个算法都轻轻一点, 对每个算法的兴趣刚刚调动起来, 一章就戛然而止.</li>
<li>图解方面也不尽人意, 不是在用可视化讲算法, 而是在用可视化讲生活示例, 图解是种极好的方式, 旨在于将复杂的算法简单化, 本书名为"算法图解", 却将图解用于调动读者的趣味性方面, 有些丢芝麻捡西瓜的味道.</li>
<li>亦或是这来源于中西方文化的差异, 中国人读书(尤其是技术/实用性书籍), 尤以功利性为目的, 在当前这个时代环境下这点只会被无限放大, 仿佛读了这本书, 我本就是以一种非休闲娱乐的目的来读的, 那如果我没有从中学到我想要的知识, 便是一种吃亏, 对时间/精力价值的亏损.</li>
<li>西方读者大抵没这么功利化吧, 所以作者的图片以趣味性为第一导向.</li>
<li>倒也无妨, 这本书的Chapter 9 动态规划还是值得一读的.</li>
<li>总而言之, 是一本不适合计算机本专业读者来读的所谓的图解算法书(C9动态规划一章除外), 作为面对大众的算法类科普也勉勉强强, 慎入吧.</li>
</ul>
</div></div>
<div class="text">
<h1>Text</h1>
<ul>
<li><a href="https://weread.qq.com/web/reader/fbf32b80715c0184fbff41fkc81322c012c81e728d9d180">微信读书</a></li>
<li>强烈建议你手动执行示例代码, 及时做好书中练习.</li>
<ul>
<li>这点我深有感触, 以前的大多半途而废就是来自于学习的过程太过轻松, 给自己设定的目标, 呵, 哪有什么目标, 只是读, 只是听, 主动性投入过少, 导致进行到中段时丧失兴趣, 对什么都一知半解.</li>
</ul>
<li>本书代码用Python2. 7做示例.</li>
<li>享受学习的过程, 重于一切</li>
</ul>
<div class="h2i1">
<h2>C1 Brief introduction of algorithm</h2>
<ul>
<li>从二分查找开始讲起, python的一些语法和我常用的语言有些区别</li>
<ul>
<li>代码块的区分从大括号转换为缩进</li>
<li>语句结尾不用写分号</li>
<li>null->None</li>
<li>while/if condition : 的格式. </li>
</ul>
<li>大O表示法, 不主要关注算法有多快, 也就是不以秒为单位来衡量, 而是关注时间如何随n增长.</li>
<ul>
<li>指出了算法运行时间的增速</li>
<li>大O表示法指出了最坏情况下的运行时间, C4将讨论平均时间</li>
<li>线性时间(linear time) O(n)</li>
<li>对数时间(log时间) O(logn)</li>
<li>O(logn), O(n), O(nlogn), O(n^2), O(n!)</li>
</ul>
<li>旅行商问题: 前往五个城市, 要求旅程最短. O(n!)</li>
</ul>
</div><div class="h2i2">
<h2>C2 Selection sort</h2>
<ul>
<li>从数组与链表的差别入手, 数组读取O(1), 插入/删除O(n), 链表读取O(n), 插入/删除O(1)</li>
<li>数组, 随机访问O(1), 链表, 顺序访问O(n)</li>
<li>讲了一下选择排序</li>
<li>这章结束了, 很新手向的书, 哈</li>
</ul>
</div><div class="h2i3">
<h2>C3 Recursion</h2>
<ul>
<li>很多递归都能用非递归来实现, 如果使用循环, 程序的性能可能更高, 如果使用递归, 程序可能更容易理解.</li>
<li>base case + recursive case</li>
<ul>
<li>什么时候不再调用自己, 以及 什么时候继续调用自己</li>
</ul>
<li>call stack: 调用另一个函数时, 当前函数暂停并处于未完成状态</li>
<li>递归的调用栈可能很长, 尾递归是种方法, 但并非所有语言都支持, 本书不讨论</li>
<li>读书不求将所有自己未知的信息都详细记录, 这个过程中获得了怎样智慧重于向大脑中记忆了怎样知识</li>
</ul>
</div><div class="h2i4">
<h2>C4 Quick sort</h2>
<ul>
<li>本章算法, 快排, 本章思想, 分而治之divide and conquer (D&C)</li>
<ul>
<li>D&C并非用于解决问题的算法, 而是一种解决问题的思路.</li>
</ul>
<li>e. g. int sum = [2, 4, 6]; 如何求和?</li>
<ul>
<li>这还用问么, 循环嘛, 没错, 但对于一些诸如Haskell之类的函数式编程语言, 没有循环这种东西, 如何解决这个问题呢?</li>
<li>使用递归来解决这个问题, 所以循环问题可用递归解, Q?</li>
</ul>
<li>快速排序, 最坏O(n^2), 平均O(nlogn), 推荐随机选择key</li>
</ul>
</div><div class="h2i5">
<h2>C5 散列表</h2>
<ul>
<li>hash table</li>
<ul>
<li>hash函数, 输入映射为数字</li>
<li>确定性, 不能输入两次一样的东西, 得到的结果不同</li>
<li>最好不同的输入映射为不同的结果</li>
</ul>
<li>Python中的字典就是散列表, a = dict(), b = {}</li>
<li>散列表适合用于</li>
<ul>
<li>模拟映射关系</li>
<li>防止重复</li>
<li>缓存数据(e. g. web服务器上)</li>
</ul>
<li>collision, 冲突</li>
<ul>
<li>填装因子 = 散列表包含的元素个数 / 位置总数</li>
</ul>
</ul>
</div><div class="h2i6">
<h2>C6 BFS</h2>
<ul>
<li>BFS, breadth-first search</li>
<li>最短路径问题(shortest-path problem)</li>
<ul>
<li>BFS回答两类问题, 路径存在么, 如果存在的话哪条最短</li>
</ul>
<li>O(V+E)</li>
</ul>
</div><div class="h2i7">
<h2>C7 Dijkstra</h2>
<ul>
<li>加权图中的最短路径, 适用于有向无环图(directed acyclic graph, DAG)</li>
<ul>
<li>Dijkstra不适用于带负权边的图, 因为它认为: 对于处理过的节点没有前往它的更短路径</li>
</ul>
<li>负权边的用贝尔曼-福德算法</li>
</ul>
</div><div class="h2i8">
<h2>C8 Greedy</h2>
<ul>
<li>教室调度问题</li>
<ul>
<li>选出结束最早的课为第一节, 选出第一节之后开始的结束最早的为第二节,...</li>
</ul>
<li>贪心, 每步都选择局部最优解, 最终得到全局最优解</li>
<li>背包问题, 用贪心得到的不一定是最优解, 只能说是近似解</li>
<li>有些情况下, 完美是优秀的敌人</li>
<li>NP完全问题: 需要计算所有的接, 选出最优解</li>
<ul>
<li>旅行商问题, O(n!)</li>
</ul>
<li>面临NP完全问题, 还没有找到快速解决方案, 最佳的做法是使用近似算法, e. g. 贪心</li>
</ul>
</div><div class="h2i9">
<h2>C9 动态规划</h2>
<ul>
<li>Q: 动态规划和分而治之有什么区别, 不都是大问题转换为相同情况规模更小的子问题么.</li>
<ul>
<li>动态规划先解决子问题, 再逐步解决大问题.</li>
</ul>
<li>table[i][j] = max{table[i-1][j], 当前商品的价值 + 剩余空间的价值(table[i-1][j-当前商品的重量])}</li>
<li>对动态规划有了一定的认识, 就凭这一章, 这本书读起来就不亏了.</li>
<li>动态规划的子问题必须是离散的, 不能彼此间存在依赖.</li>
<li>动态规划帮助在给定约束条件下找到最优解.</li>
<li>每种动态规划解决方案都涉及网格.</li>
<li>单元格中的值通常就是你要优化的值.</li>
<li>每个单元格都是一个子问题, 因此应考虑如何将问题分成子问题.</li>
<li>最长公共子串和最长公共子序列, 都可动态规划</li>
<ul>
<li>前者hish和fish, 后者fosh和fish, 与diff类型</li>
</ul>
</ul>
</div><div class="h2i10">
<h2>C10 KNN</h2>
<ul>
<li>k-nearest neighbours, KNN</li>
<li>特征抽取与回归</li>
<ul>
<li>苹果和香蕉</li>
<li>特征: 颜色, 形状</li>
<li>一个东西, 有点像苹果也有点像香蕉, 那到底计算机认为它是什么</li>
<li>把它的颜色和形状放到坐标轴上, 找离他最近的k个样本, 多数是什么就认为它是什么</li>
<li>这就是分类</li>
</ul>
<li>使用KNN可以做分类与回归</li>
<ul>
<li>分类就是对其分组</li>
<li>回归就是预测结果</li>
</ul>
<li>KNN算是入门机器学习领域的入门算法</li>
<li>还有一些其他例子</li>
<li>OCR(optical character recognition)</li>
<ul>
<li>光学字符识别</li>
<li>大量数据, 提取特征, 训练, 然后测试</li>
</ul>
<li>垃圾邮件过滤器, 朴素贝叶斯分类器</li>
<ul>
<li>先用数据训练, 这个主题的你认为它是垃圾邮件吗</li>
<li>朴素贝叶斯分类器能计算出邮件为垃圾邮件的概率</li>
</ul>
</ul>
</div>	</div>
<script src="../style/js/particles.min.js"></script>
<script src="../style/js/particles.config.js"></script>
</body>
</html>
